package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1711. 大餐计数
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/25 10:33
 */
public class CountPairs {

    public int countPairs(int[] deliciousness) {
        int maxVal = 0;
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal, val);
        }
        int maxSum = maxVal * 2;
        long sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int val : deliciousness) {
            for (int all = 1; all <= maxSum; all <<= 1) {
                int count = map.getOrDefault(all - val, 0);
                sum = (sum + count) % 1000000007;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return (int) sum;
    }

}
